package com.zlk.algorithm.huawei.leetcode.doubblePointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @program: algorithm
 * @ClassName Code06_threeSum
 * @description:
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
 * 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
 * 请你返回所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 * @author: slfang
 * @create: 2025-01-02 15:02
 * @Version 1.0
 **/
public class Code06_threeSum {

    /**
     * 任意一个三元组的和都为 0。如果我们直接使用三重循环枚举三元组，会得到 O(N
     * 3
     *  ) 个满足题目要求的三元组（其中 N 是数组的长度）时间复杂度至少为 O(N
     * 3
     *  )。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，
     *  又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此我们要换一种思路来考虑这个问题。
     *
     *「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：
     * 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
     * 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
     *
     * 也就是说，我们枚举的三元组 (a,b,c) 满足 a≤b≤c，保证了只有 (a,b,c) 这个顺序会被枚举到，
     * 而 (b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，
     * 随后使用普通的三重循环就可以满足上面的要求。
     *
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // 先排序
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            // 跳过重复元素
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // 双指针，目标是找到 nums[l] + nums[r] = -nums[i]
            int l = i + 1, r = nums.length - 1;
            int target = -nums[i];
            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++;
                    r--;
                    // 跳过重复元素
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return res;
    }
    //超出时间限制
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums.length<3){
            return ans;
        }
        int n = nums.length;
        HashSet<String> exist = new HashSet<>();
        //dp 含义 0-i 0-j 0-z范围 累加和是否等于true
        for (int i = 0; i <n ; i++) {
            for (int j = 0; j < n; j++) {
                if(j==i){
                    continue;
                }
                for (int z = 0; z < n; z++) {
                    if(z==i||z==j){
                        continue;
                    }
                    if(nums[i]+nums[j]+nums[z]==0){
                        Integer[] temp = new Integer[]{nums[i],nums[j],nums[z]};
                        Arrays.sort(temp);
                        String hashKey = Arrays.toString(temp);
                        if(!exist.contains(hashKey)){
                            exist.add(hashKey);
                            ans.add(Arrays.asList(temp));
                        }
                    }
                }
            }
        }
        return ans;
    }

}
